package com.example.leetcode;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * 奇数和偶数的情况不一样！
 */
public class Code05 {
    public static void main(String[] args) {
        Code05 code05 = new Code05();
        System.out.println(code05.longestPalindrome("a"));
        System.out.println(code05.longestPalindrome("aacabdkacaa"));
        System.out.println(code05.longestPalindrome("babad"));
        System.out.println(new Code05().longestPalindrome("cbbd"));
        System.out.println(code05.longestPalindrome("bb"));
        System.out.println(code05.longestPalindrome("aaaa"));
        System.out.println(code05.longestPalindrome("aaaaa"));
        System.out.println(code05.longestPalindrome("aaaaaa"));
//        System.out.println(code05.getLongestPalindromeSubsequenceLength("babad"));
//        System.out.println(code05.getLongestPalindromeSubsequenceLength("bb"));
//        System.out.println(code05.getLongestPalindromeSubsequenceLength("bc"));
//        System.out.println(code05.getLongestPalindromeSubsequenceLength("bcb"));
        // "aaca bdk acaa"
    }

    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty() || s.length() == 1) {
            return s;
        }

        int l, r;
        int ans = 1;
        String res = String.valueOf(s.charAt(0));
        // 统一处理成奇数
        //s = s.length() % 2 == 0 ? (s + "#") : s;

        for (int i = 1; i < s.length(); i++) {
            int curMax = 1;
            String str = String.valueOf(s.charAt(i));
            l = i - 1;
            r = i + 1;
            while (l >= 0 && r < s.length()) {
                if (s.charAt(l) == s.charAt(r)) {
                    curMax += 2;
                    str = s.charAt(l) + str + s.charAt(r);
                    if (curMax > ans) {
                        ans = curMax;
                        res = str;
                    }
                    l--;
                    r++;
                } else {
                    break;
                }
            }
        }
        for (int i = 0; i < s.length(); i++) {
            int curMax = 0;
            String str = "";
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.length()) {
                if (s.charAt(l) == s.charAt(r)) {
                    curMax += 2;
                    str = s.charAt(l) + str + s.charAt(r);
                    if (curMax > ans) {
                        ans = curMax;
                        res = str;
                    }
                    l--;
                    r++;
                } else {
                    break;
                }
            }
        }
        return res;
    }

    //private

    public String getLongestPalindromeSubsequenceLength(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        if (str.length() == 1) {
            return str;
        }
        if (str.length() == 2) {
            if (str.charAt(0) == str.charAt(1)) {
                return str;
            } else {
                return String.valueOf(str.charAt(0));
            }
        }
        final char[] chars = str.toCharArray();
        String ans = "";
        process(chars, 0, chars.length - 1, ans);
        return ans;
    }

    public void process(char[] chars, int left, int right, String ans) {
        if (left == right) {
            ans = String.valueOf(chars[left]);
            //return 1;
            return;
        }
        if (chars[left] == chars[right]) { //abba
            ans = chars[left] + ans + chars[right];
            process(chars, left + 1, right - 1, ans);
        } else {
            process(chars, left + 1, right, ans);
            process(chars, left, right - 1, ans);
        }
    }
}
